package leetcode_200;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import helpclass.TreeNode;

/**
 *@author 周杨
 *BinaryTreeRightSideView_199 假设站在一棵树的右边 输出你看到整棵树从上到下的集合
 *describe:用层次遍历 每次记录每层最右边的一个元素  AC 50%
 *2018年6月11日 上午9:53:09
 */
public class BinaryTreeRightSideView_199 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	
	public List<Integer> rightSideView(TreeNode root) {
		List<Integer> res=new ArrayList<Integer>();
		if(root==null)
			return res;
		Queue<TreeNode> queue=new LinkedList<TreeNode>();
		queue.add(root);
		while(!queue.isEmpty()) {
			int len=queue.size();
			while(len>0) {
				TreeNode now= queue.poll();
				if(len==1) {
					res.add(now.val);
				}
				if(now.left!=null)
					queue.add(now.left);
				if(now.right!=null)
					queue.add(now.right);
				--len;
			}
		}
		return res;
    }

}
